//package java_cup.runtime;

//import java.util.Arrays;
//import java.util.LinkedList;
//import java.util.List;

public class SyntaxTreeXPath {
    public List<XMLElement> query(String query, XMLElement element) {
        if (query.StartsWith("/"))
            query = query.Substring(1);
        return query0(new List<string>(query.Split("/")), 0, element, 0);
    }

    public List<XMLElement> query0(List<String> q, int idx, XMLElement element, int seq) {

        if (q[idx] == "") { // match deeper descendant q[1]
            return matchDeeperDescendant(q, idx + 1, element, seq);
        }
        List<XMLElement> l = new();

        if (!match(q[idx], element, seq))
            return new();
        if (q.Count - 1 == idx)
            return singleton(element);
        List<XMLElement> children = element.getChildren();
        for (int i = 0; i < children.Count; i++) {
            XMLElement child = children[i];
            l.AddRange(query0(q, idx + 1, child, i));
        }
        return l;
    }

    public List<XMLElement> matchDeeperDescendant(List<String> query, int idx, XMLElement element, int seq) {
        if (query.Count <= idx)
            return singleton(element);
        bool matches = match(query[idx], element, seq);
        List<XMLElement> l = new();
        List<XMLElement> children = element.getChildren();
        if (matches)
            return query0(query, idx, element, seq);
        for (int i = 0; i < children.Count; i++) {
            XMLElement child = children[i];
            l.AddRange(matchDeeperDescendant(query, idx, child, i));
        }
        return l;
    }

    public bool match(String m, XMLElement elem, int seq) {
        // System.Console.WriteLine("Matching "+elem.tagname+" with "+m);
        bool result = true;
        //String[] name = m.split("\\[");
        //String[] tag = name[0].split("\\*");
        //if (tag[0] == "") { // start is wildcard
        //    if (tag.Length > 2)
        //        result &= elem.tagname.contains(tag[1]);
        //    else if (tag.Length == 2)
        //        result &= elem.tagname.EndsWith(tag[1]);
        //    else
        //        result &= false;
        //}
        //else { // match with start
        //    if (tag.Length == 2)
        //        result &= elem.tagname.StartsWith(tag[1]);
        //    else
        //        result = elem.tagname.Equals(tag[0]);
        //}
        //for (int i = 1; i < name.Length; i++) {
        //    String predicate = name[i];
        //    if (!predicate.EndsWith("]"))
        //        return false;
        //    predicate = predicate.Substring(0, predicate.Length - 1);

        //    if (predicate.StartsWith("@")) {
        //        if (predicate.Substring(1).StartsWith("variant"))
        //            if ((elem is XMLElement.NonTerminalXml)
        //                    && int.Parse(predicate.Substring(9)) == ((XMLElement.NonTerminalXml)elem).getVariant())
        //                result &= true;
        //            else
        //                return false;
        //        else
        //            return false;
        //    }
        //    else if (predicate.matches("\\d+")) {
        //        result &= int?.parseInt(predicate) == seq;
        //    }
        //    else
        //        return false; // submatch
        //}
        return result;
    }

    public List<XMLElement> singleton(XMLElement elem) {
        List<XMLElement> l = new();
        l.Add(elem);
        return l;
    }
}
